0438. 找到字符串中所有字母异位词【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 滑动窗口

1. 📝 题目描述

• leetcode

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

字母异位词

字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

示例 1：

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2：

输入: s = "abab", p = "ab"
输出: [0,1,2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

---

提示：

• 1 <= s.length, p.length <= 3 * 10^4
• s 和 p 仅包含小写字母

2. 🎯 s.1 - 滑动窗口

c

int* findAnagrams(char* s, char* p, int* returnSize) {
    int sLen = strlen(s), pLen = strlen(p);
    *returnSize = 0;
    int* res = (int*)malloc(sizeof(int) * sLen);
    if (sLen < pLen) return res;
    int count[26] = {0}, window[26] = {0};
    for (int i = 0; i < pLen; i++) count[p[i] - 'a']++;
    for (int i = 0; i < sLen; i++) {
        window[s[i] - 'a']++;
        if (i >= pLen) window[s[i - pLen] - 'a']--;
        if (i >= pLen - 1 && memcmp(count, window, sizeof(count)) == 0)
            res[(*returnSize)++] = i - pLen + 1;
    }
    return res;
}

js

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  const res = []
  if (s.length < p.length) return res
  const count = new Array(26).fill(0)
  for (const ch of p) count[ch.charCodeAt(0) - 97]++
  const window = new Array(26).fill(0)
  for (let i = 0; i < s.length; i++) {
    window[s.charCodeAt(i) - 97]++
    if (i >= p.length) window[s.charCodeAt(i - p.length) - 97]--
    if (i >= p.length - 1) {
      let match = true
      for (let j = 0; j < 26; j++)
        if (count[j] !== window[j]) {
          match = false
          break
        }
      if (match) res.push(i - p.length + 1)
    }
  }
  return res
}

py

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = []
        if len(s) < len(p):
            return res
        count = [0] * 26
        window = [0] * 26
        for ch in p:
            count[ord(ch) - 97] += 1
        for i in range(len(s)):
            window[ord(s[i]) - 97] += 1
            if i >= len(p):
                window[ord(s[i - len(p)]) - 97] -= 1
            if i >= len(p) - 1 and window == count:
                res.append(i - len(p) + 1)
        return res

• 时间复杂度：$O(n+m)$，其中 $n$、$m$ 分别是 $s$、$p$ 的长度
• 空间复杂度：$O(|\mathrm{\Sigma }|)$

算法思路：

• 维护长度为 $|p|$ 的滑动窗口，统计窗口内字符频率
• 当窗口频率与 $p$ 的频率相同时记录起始位置